package interview;

public class interview_04_08 {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        TreeNode[] result=new TreeNode[1];
        common(root,p,q,result);
        return result[0];
    }
    public boolean common(TreeNode node,TreeNode p,TreeNode q,TreeNode[] result){
        if(node==null) return false;
        boolean left=common(node.left, p, q,result);
        boolean right=common(node.right,p,q,result);
        if(node==p||node==q){
            if (left||right){
                result[0]=node;
            }
            return true;
        }
        else{
            if(left&&right){
                result[0]=node;
            }
            return left||right;
        }
    }
}
